package algorithm.circle;



/**
 * @author shenenlu 2021年06月07日 下午14:51:24
 */
public class JosephCircle {


    /**
     * 数组模拟解法
     * peopleCount指的是总人数，value指的是每次最大报到的数值，该函数每次可以返回最后存活的人在原一维数组中的下标
     *
     * @param peopleCount
     * @param value
     * @return
     */
    static int josephCircleArray(int peopleCount, int value){
        int[] people = new int[peopleCount];
        for(int i=0; i<peopleCount; i++){
            people[i] = 1;
        }

        int i=0;
        int currentCallNumber = 1;
        while (peopleCount != 0) {
            if (currentCallNumber == value && people[i] == 1) {
                people[i] = 0;
                currentCallNumber = 1;
                --peopleCount;
            } else if (people[i] == 1) {
                currentCallNumber++;
            }
            i++;
            //处理环形,从0开始
            i = i % peopleCount;
        }
        return i;
    }


    static int josephCircleRecursive(int sum, int value, int n){
        if(n==1)
            return (sum + value -1) % sum;
        else
            return (josephCircleRecursive(sum-1, value,n-1) + value) % sum;
    }


    public static void main(String[] args) {
        System.out.println(josephCircleRecursive(2, 2, 1));
    }


}
